class dfs_pruning:
    def __init__(self, map, t):
        self.map = map
        self.m = len(map)
        self.n = len(map[0])
        self.t = t
        self.vis = [[0 for _ in range(self.n)] for _ in range(self.m)]
        self.directions = [[1,0],[-1,0],[0,1],[0,-1]]
        self.flag = False
        self.endx = -1
        self.endy = -1
        self.startx = -1
        self.starty = -1
        for i in range(self.m):
            for j in range(self.n):
                if self.map[i][j] == 'D':
                    self.endx = i
                    self.endy = j
                if self.map[i][j] == 'S':
                    self.startx = i
                    self.starty = j
    
    def judge(self, x, y):
        if x < 0 or x > self.m - 1 or y < 0 \
            or y > self.n - 1 or self.map[x][y] == 'X' \
            or self.vis[x][y] :
            return False
        return True
    
    def dfs(self, x0, y0, time):
        if self.map[x0][y0] == 'D':
            if time == self.t:
                self.flag = True
                return
            return 
        if self.flag :
            return
        step = abs(x0 - self.endx) + abs(y0 - self.endy)
        if (self.t - step - time) % 2 == 1 or step + time > self.t:
            return 

        for i in range(4):
            x = x0 + self.directions[i][0]
            y = y0 + self.directions[i][1]
            if self.judge(x, y):
                print("A")
                self.vis[x][y] = 1
                time += 1
                self.dfs(x, y, time)
                time -= 1


##################### 

# Pruning
# if __name__ == "__main__":
#     maps = [
#         ["S",".","X","."],
#         [".",".","X","."],
#         [".",".",".","D"]]
#         # [".",".",".","."]]
#     time = 5
        
#     Solver = bfs_pruning(maps, time)
#     begins = abs(Solver.endx-Solver.startx) \
#         + abs(Solver.starty-Solver.endy)
#     if (begins + time)% 2 != 0:
#         print("NO!")
#     Solver.dfs(Solver.startx, Solver.starty, 0)
#     print(Solver.flag)

    


